Bioinformatics An Introduction 4th Edition (Jeremy Ramsden)

144

Systems and Networks

these new interconnexions, but restore the functions to those represented by (12.11)

and Table 12.1. Compare the results with each other and with Fig. 12.1.

12.1.2

Cellular Automata

This term is usually applied to cells arranged in spatial proximity to each other,

whose states are updated according to a rule such asn prime Subscript i Baseline equals left parenthesis n Subscript i minus 1 Baseline plus n Subscript i Baseline plus n Subscript i plus 1 Baseline right parenthesis mod 2n^,

i ⁼⁽ⁿⁱ⁻¹⁺ⁿⁱ⁺ⁿⁱ⁺¹⁾^{mod 2,}

where n Subscript ini is the current state of the iith cell. The most widely studied ones are only

connected to their nearest neighbours. Despite this simplicity, their evolution can be

rather elaborate and even unpredictable. Wolfram (1983) has made an exhaustive

study of one-dimensional cellular automata, in which the cells are arranged on a

line. Higher dimensional automata are useful in analysing biological processes; for

example a two-dimensional automaton has been used to investigate neurogenesis

in a membrane of undifferentiated precursor cells. ⁷Sree et al. (2014) review other

applications in bioinformatics, such as predicting protein coding and promoter DNA

sequences.

12.1.3

Percolation

Consider a spatial array of at least two dimensions, with cells able to take values of

zero or one, signifying respectively “impermeable” and “permeable” to some agent

migrating across the array and only able to move from a permeable site to the nearest

neighbour that is also permeable. Letpp be the probability that a cell has the value 1.

If ones are sparse (i.e., low pp), the mobility of the agent will be restricted to small

isolated islands. The most important problem in this ﬁeld is to determine the mean

value of pp at which an agent can span the entire array via its nearest neighbour

connexions. This is so-called “site percolation”. ⁸

A possible approach to determine the critical valuep Subscript cpc is as follows: the probability

that a single permeable cell on a square lattice is surrounded by impermeable ones

(i.e., is a singlet) isp q Superscript 4pq⁴, whereq equals 1 minus pq = 1 −p. Deﬁningn Subscript s Baseline left parenthesis p right parenthesisns(p)to be the average number of

ss-clusters per cell, we haven 2 left parenthesis p right parenthesis equals 2 p squared q Superscript 6n2(p) = 2p²q⁶for doublets (the factor 2 arises because of

the two possible perpendicular orientations of the doublet),n 3 left parenthesis p right parenthesis equals 2 p cubed q Superscript 8 Baseline plus 4 p cubed q Superscript 7n3(p) = 2p³q⁸+ 4p³q⁷

for triplets (linear and bent), etc. If there are few permeable cells, sigma summation Underscript s Endscripts s n Subscript s Baseline left parenthesis p right parenthesis equals p^Σ

s ^sn^s⁽^p⁾⁼^p^;

if there are many, we can expect most of the particles to belong to an inﬁnite (in the

limit of an inﬁnite array) cluster, hencesigma summation Underscript s Endscripts s n Subscript s Baseline left parenthesis p right parenthesis plus upper P Subscript normal infinity Baseline equals p^Σ

s ^sn^s⁽^p⁾⁺^P^∞⁼^p^{, and the mean cluster}

size upper S left parenthesis p right parenthesis equals sigma summation Underscript s Endscripts s squared n Subscript s Baseline left parenthesis p right parenthesis divided by pS(p) = ^Σ

s ^s²ⁿ^s⁽^p^)/^p^{. If}^{upper S left parenthesis p right parenthesis}^S⁽^p⁾^{is now expanded in powers of}^p^p^{, one ﬁnds that}

at a certain value ofpp the series diverges; this is when the inﬁnite (spanning) cluster

7 Luthi et al. (1998).

8 In “bond percolation”, movement occurs along links joining nearest neighbours with probability

pp. Every bond process can be converted into a site one, but not every site process is a bond one.